/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年04月09日
*   描    述：
*
================================================================*/
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
  int val;
  struct ListNode *next;
};

typedef struct Node {
  int key;
  void *value;
  struct Node *next;
} Node;

typedef struct Map {
  Node **buckets;
  int size;
} Map;

// 创建一个新的节点
Node *createNode(int key, void *value) {
  Node *node = (Node *)malloc(sizeof(Node));
  if (node == NULL) {
    perror("Error: unable to allocate memory for new node.");
    exit(EXIT_FAILURE);
  }
  node->key = key;
  node->value = value;
  node->next = NULL;
  return node;
}

// 删除一个节点
void deleteNode(Node *node) { free(node); }

// 计算哈希值
int hash(int key, int size) {
  int hash = 0;
  hash = 31 * hash + key;
  return abs(hash % size);
}

// 创建一个新的 Map
Map *CreateMap(int size) {
  Map *map = (Map *)malloc(sizeof(Map));
  if (map == NULL) {
    perror("Error: unable to allocate memory for new map.");
    exit(EXIT_FAILURE);
  }
  map->size = size;
  map->buckets = (Node **)calloc(size, sizeof(Node *));
  if (map->buckets == NULL) {
    perror("Error: unable to allocate memory for buckets.");
    exit(EXIT_FAILURE);
  }
  return map;
}

// 删除一个 Map
void DeleteMap(Map *map) {
  int i = 0;
  for (; i < map->size; ++i) {
    Node *node = map->buckets[i];
    while (node != NULL) {
      Node *tmp = node;
      node = node->next;
      deleteNode(tmp);
    }
  }
  free(map->buckets);
  free(map);
}

// 添加键值对
void Put(Map *map, int key, void *value) {
  int idx = hash(key, map->size);
  Node *node = map->buckets[idx];
  while (node != NULL) {
    if (node->key == key) {
      node->value = value;
      return;
    }
    node = node->next;
  }
  node = createNode(key, value);
  node->next = map->buckets[idx];
  map->buckets[idx] = node;
}

// 获取键对应的值，如果不存在则返回 NULL
void *Get(Map *map, int key) {
  int idx = hash(key, map->size);
  Node *node = map->buckets[idx];
  while (node != NULL) {
    if (node->key == key) return node->value;
    node = node->next;
  }
  return NULL;
}

struct ListNode *detectCycle(struct ListNode *head) {
  if (head == NULL || head->next == NULL) {
    return NULL;
  }

  Map *_map = CreateMap(20000);
  struct ListNode *fastNode = head, *slowNode = head;
  Put(_map, (int)slowNode, slowNode);
  while (1) {
    slowNode = slowNode->next;
    fastNode = fastNode->next;
    if (fastNode == NULL) {
      break;
    }
    fastNode = fastNode->next;
    if (fastNode == NULL) {
      break;
    }

    if (Get(_map, (int)slowNode) != NULL) {
      return slowNode;
    }

    Put(_map, (int)slowNode, slowNode);
  }
  DeleteMap(_map);

  return NULL;
}

int main() {
  struct ListNode *currNode = NULL;
  struct ListNode *listA = (struct ListNode *)malloc(sizeof(struct ListNode));

  listA->val = 1;
  listA->next = (struct ListNode *)malloc(sizeof(struct ListNode));
  currNode = listA->next;

  currNode->val = 2;
  currNode->next = (struct ListNode *)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 3;
  currNode->next = (struct ListNode *)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 4;
  currNode->next = (struct ListNode *)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 5;
  currNode->next = listA->next->next;

  printf("%d\n", detectCycle(listA)->val);
  return 0;
}
